﻿// 4943. 方格迷宫.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


/*
https://www.acwing.com/problem/content/4946/


给定一个 n
 行 m
 列的方格矩阵。

行从上到下依次编号为 1∼n
，列从左到右依次编号为 1∼m
。

第 i
 行第 j
 列的方格表示为 (i,j)
。

矩阵中的方格要么是空地（用 . 表示），要么是陷阱（用 # 表示）。

初始时，你位于方格 (x1,y1)
，你需要前往方格 (x2,y2)
。

每次移动，你可以任选上、下、左、右四个方向之一，并沿该方向移动 1∼k
 步。

从一个方格移动至相邻方格视为一步。

但是，你要保证在你的移动过程中不能走出矩阵，也不能进入陷阱方格。

请你计算从方格 (x1,y1)
 移动至方格 (x2,y2)
，所需要的最少移动次数。

保证方格 (x1,y1)
 和方格 (x2,y2)
 都是空地。

方格 (x1,y1)
 和方格 (x2,y2)
 可能是同一个方格。

注意：注意区分本题中移动次数与移动步数的区别。

输入格式
第一行包含三个整数 n,m,k
。

接下来 n
 行，每行包含 m
 个字符，其中第 i
 行第 j
 个字符，要么是 .，表示方格 (i,j)
 是空地；要么是 #，表示方格 (i,j)
 是陷阱。

最后一行包含四个整数 x1,y1,x2,y2
。

输出格式
一个整数，表示所需要的最少移动次数。

如果无法从方格 (x1,y1)
 移动至方格 (x2,y2)
，则输出 -1。

数据范围
前 6
 个测试点满足 1≤n,m≤10
。
所有测试点满足 1≤n,m,k≤1000
，1≤x1,x2≤n
，1≤y1,y2≤m
。

输入样例1：
3 4 4
....
###.
....
1 1 3 1
输出样例1：
3
输入样例2：
3 4 1
....
###.
....
1 1 3 1
输出样例2：
8
输入样例3：
2 2 1
.#
#.
1 1 2 2
输出样例3：
-1
*/
int main()
{
    std::cout << "Hello World!\n";
}

 